home *** CD-ROM | disk | FTP | other *** search
/ MacFormat 1994 November / macformat-018.iso / Utility Spectacular / Developer / Marlais 0.3.1 / gc4.1-mac / cord / cordxtra.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-07-26  |  15.3 KB  |  567 lines  |  [TEXT/R*ch]
  1. /*
  2.  * Copyright (c) 1993-1994 by Xerox Corporation.  All rights reserved.
  3.  *
  4.  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
  5.  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
  6.  *
  7.  * Permission is hereby granted to use or copy this program
  8.  * for any purpose,  provided the above notices are retained on all copies.
  9.  * Permission to modify the code and to distribute modified code is granted,
  10.  * provided the above notices are retained, and a notice that the code was
  11.  * modified is included with the above copyright notice.
  12.  *
  13.  * Author: Hans-J. Boehm (boehm@parc.xerox.com)
  14.  */
  15. /*
  16.  * These are functions on cords that do not need to understand their
  17.  * implementation.  They serve also serve as example client code for
  18.  * cord_basics.
  19.  */
  20. /* Boehm, May 19, 1994 2:18 pm PDT */
  21. # include <stdio.h>
  22. # include <string.h>
  23. # include <stdlib.h>
  24. # include "cord.h"
  25. # include "ec.h"
  26. # define I_HIDE_POINTERS    /* So we get access to allocation lock.    */
  27.                 /* We use this for lazy file reading,     */
  28.                 /* so that we remain independent     */
  29.                 /* of the threads primitives.        */
  30. # include "gc.h"
  31.  
  32. /* The standard says these are in stdio.h, but they aren't always: */
  33. # ifndef SEEK_SET
  34. #   define SEEK_SET 0
  35. # endif
  36. # ifndef SEEK_END
  37. #   define SEEK_END 2
  38. # endif
  39.  
  40. # define BUFSZ 2048    /* Size of stack allocated buffers when        */
  41.             /* we want large buffers.            */
  42.  
  43. typedef void (* oom_fn)(void);
  44.  
  45. # define OUT_OF_MEMORY {  if (CORD_oom_fn != (oom_fn) 0) (*CORD_oom_fn)(); \
  46.               ABORT("Out of memory\n"); }
  47. # define ABORT(msg) { fprintf(stderr, "%s\n", msg); abort(); }
  48.  
  49. CORD CORD_cat_char(CORD x, char c)
  50. {
  51.     register char * string;
  52.     
  53.     if (c == '\0') return(CORD_cat(x, CORD_nul(1)));
  54.     string = GC_MALLOC_ATOMIC(2);
  55.     if (string == 0) OUT_OF_MEMORY;
  56.     string[0] = c;
  57.     string[1] = '\0';
  58.     return(CORD_cat_char_star(x, string, 1));
  59. }
  60.  
  61. typedef struct {
  62.     size_t len;
  63.     size_t count;
  64.     char * buf;
  65. } CORD_fill_data;
  66.  
  67. int CORD_fill_proc(char c, void * client_data)
  68. {
  69.     register CORD_fill_data * d = (CORD_fill_data *)client_data;
  70.     register size_t count = d -> count;
  71.     
  72.     (d -> buf)[count] = c;
  73.     d -> count = ++count;
  74.     if (count >= d -> len) {
  75.         return(1);
  76.     } else {
  77.         return(0);
  78.     }
  79. }
  80.  
  81. int CORD_batched_fill_proc(const char * s, void * client_data)
  82. {
  83.     register CORD_fill_data * d = (CORD_fill_data *)client_data;
  84.     register size_t count = d -> count;
  85.     register size_t max = d -> len;
  86.     register char * buf = d -> buf;
  87.     register const char * t = s;
  88.     
  89.     while(((d -> buf)[count] = *t++) != '\0') {
  90.         count++;
  91.         if (count >= max) {
  92.             d -> count = count;
  93.             return(1);
  94.         }
  95.     }
  96.     d -> count = count;
  97.     return(0);
  98. }
  99.  
  100. /* Fill buf with between min and max characters starting at i.      */
  101. /* Assumes len characters are available.                */ 
  102. void CORD_fill_buf(CORD x, size_t i, size_t len, char * buf)
  103. {
  104.     CORD_fill_data fd;
  105.     
  106.     fd.len = len;
  107.     fd.buf = buf;
  108.     fd.count = 0;
  109.     (void)CORD_iter5(x, i, CORD_fill_proc, CORD_batched_fill_proc, &fd);
  110. }
  111.  
  112. int CORD_cmp(CORD x, CORD y)
  113. {
  114.     CORD_pos xpos;
  115.     CORD_pos ypos;
  116.     register size_t avail, yavail;
  117.     
  118.     if (y == CORD_EMPTY) return(x != CORD_EMPTY);
  119.     if (x == CORD_EMPTY) return(-1);
  120.     if (IS_STRING(y) && IS_STRING(x)) return(strcmp(x,y));
  121.     CORD_set_pos(xpos, x, 0);
  122.     CORD_set_pos(ypos, y, 0);
  123.     for(;;) {
  124.         if (!CORD_pos_valid(xpos)) {
  125.             if (CORD_pos_valid(ypos)) {
  126.                 return(-1);
  127.             } else {
  128.                 return(0);
  129.             }
  130.         }
  131.         if (!CORD_pos_valid(ypos)) {
  132.             return(1);
  133.         }
  134.         if ((avail = CORD_pos_chars_left(xpos)) <= 0
  135.             || (yavail = CORD_pos_chars_left(ypos)) <= 0) {
  136.             register char xcurrent = CORD_pos_fetch(xpos);
  137.             register char ycurrent = CORD_pos_fetch(ypos);
  138.             if (xcurrent != ycurrent) return(xcurrent - ycurrent);
  139.             CORD_next(xpos);
  140.             CORD_next(ypos);
  141.         } else {
  142.             /* process as many characters as we can    */
  143.             register int result;
  144.             
  145.             if (avail > yavail) avail = yavail;
  146.             result = strncmp(CORD_pos_cur_char_addr(xpos),
  147.                          CORD_pos_cur_char_addr(ypos), avail);
  148.             if (result != 0) return(result);
  149.             CORD_pos_advance(xpos, avail);
  150.             CORD_pos_advance(ypos, avail);
  151.         }
  152.     }
  153. }
  154.  
  155. int CORD_ncmp(CORD x, size_t x_start, CORD y, size_t y_start, size_t len)
  156. {
  157.     CORD_pos xpos;
  158.     CORD_pos ypos;
  159.     register size_t count;
  160.     register long avail, yavail;
  161.     
  162.     CORD_set_pos(xpos, x, x_start);
  163.     CORD_set_pos(ypos, y, y_start);
  164.     for(count = 0; count < len;) {
  165.         if (!CORD_pos_valid(xpos)) {
  166.             if (CORD_pos_valid(ypos)) {
  167.                 return(-1);
  168.             } else {
  169.                 return(0);
  170.             }
  171.         }
  172.         if (!CORD_pos_valid(ypos)) {
  173.             return(1);
  174.         }
  175.         if ((avail = CORD_pos_chars_left(xpos)) <= 0
  176.             || (yavail = CORD_pos_chars_left(ypos)) <= 0) {
  177.             register char xcurrent = CORD_pos_fetch(xpos);
  178.             register char ycurrent = CORD_pos_fetch(ypos);
  179.             if (xcurrent != ycurrent) return(xcurrent - ycurrent);
  180.             CORD_next(xpos);
  181.             CORD_next(ypos);
  182.             count++;
  183.         } else {
  184.             /* process as many characters as we can    */
  185.             register int result;
  186.             
  187.             if (avail > yavail) avail = yavail;
  188.             count += avail;
  189.             if (count > len) avail -= (count - len);
  190.             result = strncmp(CORD_pos_cur_char_addr(xpos),
  191.                          CORD_pos_cur_char_addr(ypos), (size_t)avail);
  192.             if (result != 0) return(result);
  193.             CORD_pos_advance(xpos, (size_t)avail);
  194.             CORD_pos_advance(ypos, (size_t)avail);
  195.         }
  196.     }
  197.     return(0);
  198. }
  199.  
  200. char * CORD_to_char_star(CORD x)
  201. {
  202.     register size_t len;
  203.     char * result;
  204.     
  205.     if (x == 0) return("");
  206.     len = CORD_len(x);
  207.     result = (char *)GC_MALLOC_ATOMIC(len + 1);
  208.     if (result == 0) OUT_OF_MEMORY;
  209.     CORD_fill_buf(x, 0, len, result);
  210.     result[len] = '\0';
  211.     return(result);
  212. }
  213.  
  214. char CORD_fetch(CORD x, size_t i)
  215. {
  216.     CORD_pos xpos;
  217.     
  218.     CORD_set_pos(xpos, x, i);
  219.     if (!CORD_pos_valid(xpos)) ABORT("bad index?");
  220.     return(CORD_pos_fetch(xpos));
  221. }
  222.  
  223.  
  224. int CORD_put_proc(char c, void * client_data)
  225. {
  226.     register FILE * f = (FILE *)client_data;
  227.     
  228.     return(putc(c, f) == EOF);
  229. }
  230.  
  231. int CORD_batched_put_proc(const char * s, void * client_data)
  232. {
  233.     register FILE * f = (FILE *)client_data;
  234.     
  235.     return(fputs(s, f) == EOF);
  236. }
  237.     
  238.  
  239. int CORD_put(CORD x, FILE * f)
  240. {
  241.     if (CORD_iter5(x, 0, CORD_put_proc, CORD_batched_put_proc, f)) {
  242.         return(EOF);
  243.     } else {
  244.         return(1);
  245.     }
  246. }
  247.  
  248. typedef struct {
  249.     size_t pos;        /* Current position in the cord */
  250.     char target;    /* Character we're looking for    */
  251. } chr_data;
  252.  
  253. int CORD_chr_proc(char c, void * client_data)
  254. {
  255.     register chr_data * d = (chr_data *)client_data;
  256.     
  257.     if (c == d -> target) return(1);
  258.     (d -> pos) ++;
  259.     return(0);
  260. }
  261.  
  262. int CORD_rchr_proc(char c, void * client_data)
  263. {
  264.     register chr_data * d = (chr_data *)client_data;
  265.     
  266.     if (c == d -> target) return(1);
  267.     (d -> pos) --;
  268.     return(0);
  269. }
  270.  
  271. int CORD_batched_chr_proc(const char *s, void * client_data)
  272. {
  273.     register chr_data * d = (chr_data *)client_data;
  274.     register char * occ = strchr(s, d -> target);
  275.     
  276.     if (occ == 0) {
  277.           d -> pos += strlen(s);
  278.           return(0);
  279.     } else {
  280.         d -> pos += occ - s;
  281.         return(1);
  282.     }
  283. }
  284.  
  285. size_t CORD_chr(CORD x, size_t i, int c)
  286. {
  287.     chr_data d;
  288.     
  289.     d.pos = i;
  290.     d.target = c;
  291.     if (CORD_iter5(x, i, CORD_chr_proc, CORD_batched_chr_proc, &d)) {
  292.         return(d.pos);
  293.     } else {
  294.         return(CORD_NOT_FOUND);
  295.     }
  296. }
  297.  
  298. size_t CORD_rchr(CORD x, size_t i, int c)
  299. {
  300.     chr_data d;
  301.     
  302.     d.pos = i;
  303.     d.target = c;
  304.     if (CORD_riter4(x, i, CORD_rchr_proc, &d)) {
  305.         return(d.pos);
  306.     } else {
  307.         return(CORD_NOT_FOUND);
  308.     }
  309. }
  310.  
  311. /* Find the first occurrence of s in x at position start or later.    */
  312. /* This uses an asymptotically poor algorithm, which should typically     */
  313. /* perform acceptably.  We compare the first few characters directly,    */
  314. /* and call CORD_ncmp whenever there is a partial match.        */
  315. /* This has the advantage that we allocate very little, or not at all.    */
  316. /* It's very fast if there are few close misses.            */
  317. size_t CORD_str(CORD x, size_t start, CORD s)
  318. {
  319.     CORD_pos xpos;
  320.     size_t xlen = CORD_len(x);
  321.     size_t slen;
  322.     register size_t start_len;
  323.     const char * s_start;
  324.     unsigned long s_buf = 0;    /* The first few characters of s    */
  325.     unsigned long x_buf = 0;    /* Start of candidate substring.    */
  326.                     /* Initialized only to make compilers    */
  327.                     /* happy.                */
  328.     unsigned long mask = 0;
  329.     register size_t i;
  330.     register size_t match_pos;
  331.     
  332.     if (s == CORD_EMPTY) return(start);
  333.     if (IS_STRING(s)) {
  334.         s_start = s;
  335.         slen = strlen(s);
  336.     } else {
  337.         s_start = CORD_to_char_star(CORD_substr(s, 0, sizeof(unsigned long)));
  338.         slen = CORD_len(s);
  339.     }
  340.     if (xlen < start || xlen - start < slen) return(CORD_NOT_FOUND);
  341.     start_len = slen;
  342.     if (start_len > sizeof(unsigned long)) start_len = sizeof(unsigned long);
  343.     CORD_set_pos(xpos, x, start);
  344.     for (i = 0; i < start_len; i++) {
  345.         mask <<= 8;
  346.         mask |= 0xff;
  347.         s_buf <<= 8;
  348.         s_buf |= s_start[i];
  349.         x_buf <<= 8;
  350.         x_buf |= CORD_pos_fetch(xpos);
  351.         CORD_next(xpos);
  352.     }
  353.     for (match_pos = start; match_pos < xlen - slen; match_pos++) {
  354.         if ((x_buf & mask) == s_buf) {
  355.             if (slen == start_len ||
  356.                  CORD_ncmp(x, match_pos + start_len,
  357.                         s, start_len, slen - start_len) == 0) {
  358.                 return(match_pos);
  359.             }
  360.         }
  361.         x_buf <<= 8;
  362.         x_buf |= CORD_pos_fetch(xpos);
  363.         CORD_next(xpos);
  364.     }
  365.     return(CORD_NOT_FOUND);
  366. }
  367.  
  368. void CORD_ec_flush_buf(CORD_ec x)
  369. {
  370.     register size_t len = x[0].ec_bufptr - x[0].ec_buf;
  371.     char * s;
  372.  
  373.     if (len == 0) return;
  374.     s = GC_MALLOC_ATOMIC(len+1);
  375.     memcpy(s, x[0].ec_buf, len);
  376.     s[len] = '\0';
  377.     x[0].ec_cord = CORD_cat_char_star(x[0].ec_cord, s, len);
  378.     x[0].ec_bufptr = x[0].ec_buf;
  379. }
  380.  
  381. void CORD_ec_append_cord(CORD_ec x, CORD s)
  382. {
  383.     CORD_ec_flush_buf(x);
  384.     x[0].ec_cord = CORD_cat(x[0].ec_cord, s);
  385. }
  386.  
  387. /*ARGSUSED*/
  388. char CORD_nul_func(size_t i, void * client_data)
  389. {
  390.     return((char)(unsigned long)client_data);
  391. }
  392.  
  393.  
  394. CORD CORD_chars(char c, size_t i)
  395. {
  396.     return(CORD_from_fn(CORD_nul_func, (void *)(unsigned long)c, i));
  397. }
  398.  
  399. CORD CORD_from_file_eager(FILE * f)
  400. {
  401.     register int c;
  402.     CORD_ec ecord;
  403.     
  404.     CORD_ec_init(ecord);
  405.     for(;;) {
  406.         c = getc(f);
  407.         if (c == 0) {
  408.           /* Append the right number of NULs    */
  409.           /* Note that any string of NULs is rpresented in 4 words,    */
  410.           /* independent of its length.                    */
  411.             register size_t count = 1;
  412.             
  413.             CORD_ec_flush_buf(ecord);
  414.             while ((c = getc(f)) == 0) count++;
  415.             ecord[0].ec_cord = CORD_cat(ecord[0].ec_cord, CORD_nul(count));
  416.         }
  417.         if (c == EOF) break;
  418.         CORD_ec_append(ecord, c);
  419.     }
  420.     (void) fclose(f);
  421.     return(CORD_balance(CORD_ec_to_cord(ecord)));
  422. }
  423.  
  424. /* The state maintained for a lazily read file consists primarily    */
  425. /* of a large direct-mapped cache of previously read values.        */
  426. /* We could rely more on stdio buffering.  That would have 2        */
  427. /* disadvantages:                            */
  428. /*      1) Empirically, not all fseek implementations preserve the    */
  429. /*       buffer whenever they could.                    */
  430. /*    2) It would fail if 2 different sections of a long cord        */
  431. /*       were being read alternately.                    */
  432. /* We do use the stdio buffer for read ahead.                */
  433. /* To guarantee thread safety in the presence of atomic pointer        */
  434. /* writes, cache lines are always replaced, and never modified in    */
  435. /* place.                                */
  436.  
  437. # define LOG_CACHE_SZ 14
  438. # define CACHE_SZ (1 << LOG_CACHE_SZ)
  439. # define LOG_LINE_SZ 9
  440. # define LINE_SZ (1 << LOG_LINE_SZ)
  441.  
  442. typedef struct {
  443.     size_t tag;
  444.     char data[LINE_SZ];
  445.         /* data[i%LINE_SZ] = ith char in file if tag = i/LINE_SZ    */
  446. } cache_line;
  447.  
  448. typedef struct {
  449.     FILE * lf_file;
  450.     size_t lf_current;    /* Current file pointer value */
  451.     cache_line * volatile lf_cache[CACHE_SZ/LINE_SZ];
  452. } lf_state;
  453.  
  454. # define MOD_CACHE_SZ(n) ((n) & (CACHE_SZ - 1))
  455. # define DIV_CACHE_SZ(n) ((n) >> LOG_CACHE_SZ)
  456. # define MOD_LINE_SZ(n) ((n) & (LINE_SZ - 1))
  457. # define DIV_LINE_SZ(n) ((n) >> LOG_LINE_SZ)
  458. # define LINE_START(n) ((n) & ~(LINE_SZ - 1))
  459.  
  460. typedef struct {
  461.     lf_state * state;
  462.     size_t file_pos;    /* Position of needed character. */
  463.     cache_line * new_cache;
  464. } refill_data;
  465.  
  466. /* Executed with allocation lock. */
  467. static char refill_cache(client_data)
  468. refill_data * client_data;
  469. {
  470.     register lf_state * state = client_data -> state;
  471.     register size_t file_pos = client_data -> file_pos;
  472.     FILE *f = state -> lf_file;
  473.     size_t line_start = LINE_START(file_pos);
  474.     size_t line_no = DIV_LINE_SZ(MOD_CACHE_SZ(file_pos));
  475.     cache_line * new_cache = client_data -> new_cache;
  476.     
  477.     if (line_start != state -> lf_current
  478.         && fseek(f, line_start, SEEK_SET) != 0) {
  479.             ABORT("fseek failed");
  480.     }
  481.     if (fread(new_cache -> data, sizeof(char), LINE_SZ, f)
  482.         <= file_pos - line_start) {
  483.         ABORT("fread failed");
  484.     }
  485.     new_cache -> tag = DIV_LINE_SZ(file_pos);
  486.     /* Store barrier goes here. */
  487.     state -> lf_cache[line_no] = new_cache;
  488.     state -> lf_current = line_start + LINE_SZ;
  489.     return(new_cache->data[MOD_LINE_SZ(file_pos)]);
  490. }
  491.  
  492. char CORD_lf_func(size_t i, void * client_data)
  493. {
  494.     register lf_state * state = (lf_state *)client_data;
  495.     register cache_line * cl = state -> lf_cache[DIV_LINE_SZ(MOD_CACHE_SZ(i))];
  496.     
  497.     if (cl == 0 || cl -> tag != DIV_LINE_SZ(i)) {
  498.         /* Cache miss */
  499.         refill_data rd;
  500.         
  501.         rd.state = state;
  502.         rd.file_pos =  i;
  503.         rd.new_cache = GC_NEW_ATOMIC(cache_line);
  504.         if (rd.new_cache == 0) OUT_OF_MEMORY;
  505.         return((char)(GC_word)
  506.               GC_call_with_alloc_lock((GC_fn_type) refill_cache, &rd));
  507.     }
  508.     return(cl -> data[MOD_LINE_SZ(i)]);
  509. }    
  510.  
  511. /*ARGSUSED*/
  512. void CORD_lf_close_proc(void * obj, void * client_data)  
  513. {
  514.     if (fclose(((lf_state *)obj) -> lf_file) != 0) {
  515.         ABORT("CORD_lf_close_proc: fclose failed");
  516.     }
  517. }            
  518.  
  519. CORD CORD_from_file_lazy_inner(FILE * f, size_t len)
  520. {
  521.     register lf_state * state = GC_NEW(lf_state);
  522.     register int i;
  523.     
  524.     if (state == 0) OUT_OF_MEMORY;
  525.     state -> lf_file = f;
  526.     for (i = 0; i < CACHE_SZ/LINE_SZ; i++) {
  527.         state -> lf_cache[i] = 0;
  528.     }
  529.     state -> lf_current = 0;
  530.     GC_register_finalizer(state, CORD_lf_close_proc, 0, 0, 0);
  531.     return(CORD_from_fn(CORD_lf_func, state, len));
  532. }
  533.  
  534. CORD CORD_from_file_lazy(FILE * f)
  535. {
  536.     register size_t len;
  537.     
  538.     if (fseek(f, 0l, SEEK_END) != 0) {
  539.         ABORT("Bad fd argument - fseek failed");
  540.     }
  541.     if ((len = ftell(f)) < 0) {
  542.         ABORT("Bad fd argument - ftell failed");
  543.     }
  544.     rewind(f);
  545.     return(CORD_from_file_lazy_inner(f, len));
  546. }
  547.  
  548. # define LAZY_THRESHOLD (128*1024 + 1)
  549.  
  550. CORD CORD_from_file(FILE * f)
  551. {
  552.     register size_t len;
  553.     
  554.     if (fseek(f, 0l, SEEK_END) != 0) {
  555.         ABORT("Bad fd argument - fseek failed");
  556.     }
  557.     if ((len = ftell(f)) < 0) {
  558.         ABORT("Bad fd argument - ftell failed");
  559.     }
  560.     rewind(f);
  561.     if (len < LAZY_THRESHOLD) {
  562.         return(CORD_from_file_eager(f));
  563.     } else {
  564.         return(CORD_from_file_lazy_inner(f, len));
  565.     }
  566. }
  567.